package leetcode.editor.cn;

/**
 * 堆排序  https://www.cnblogs.com/jingmoxukong/p/4303826.html
 */
public class AHeapSort implements AIOrder{
    @Override
    public void sort(int[] nums) {
        int index = (nums.length-1)/2;
        // 建堆
        for (int i = index; i >= 0; i--) {
            adjust(nums, i, nums.length-1);
        }

        // 抛出堆顶
        for (int i = nums.length-1; i > 0 ; i--) {
            swap(nums, i, 0);
            adjust(nums, 0, i-1);
        }
    }

    // 个人
    private void adjust2(int[] nums, int index, int end) {
        int left = 2*index+1, right = left+1;
        if (left <= end && right <= end) {
            // 如果节点有左右子树
            if (nums[left] > nums[index] && nums[right] > nums[index]) {
                // 和最大的子节点进行交换
                if (nums[left] > nums[right]) {
                    swap(nums, left, index);
                    adjust(nums, left, end);
                } else {
                    swap(nums, right, index);
                    adjust(nums, right, end);
                }
            } else if (nums[left] > nums[index]) {
                swap(nums, left, index);
                adjust(nums, left, end);
            } else if (nums[right] > nums[index]) {
                swap(nums, right, index);
                adjust(nums, right, end);
            }
        } else if (left <= end) {
            // 如果节点只有左子树
            if (nums[left] > nums[index]) {
                swap(nums, left, index);
                adjust(nums, left, end);
            }
        }
    }

    // 优化
    private void adjust(int[] nums, int index, int end) {
        int temp = nums[index];
        for (int child = 2*index + 1;child <= end; child=index*2+1) {

            if (child+1 <= end && nums[child] < nums[child+1]) {
                child++;
            }

            if (nums[child] < temp) {
                break;
            }
            nums[index] = nums[child];
            index = child;
        }
        nums[index] = temp;
    }

    private void swap(int[] nums, int left, int right) {
        nums[left] ^= nums[right];
        nums[right] ^= nums[left];
        nums[left] ^= nums[right];
    }

    public static void main(String[] args) {
        AIOrder order = new AHeapSort();
//        int[] nums = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        int[] nums = new int[]{1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
        order.sort(nums);
        System.out.println("end");
    }
}
